// 最大正方形

package Leetcode;

class Solution_221 {
    public int maximalSquare(char[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = 0;

        for (int i = 0; i < matrix.length; i++)
            for (int j = 0; j < matrix[0].length; j++) {
                // 初始化
                if (i == 0 || j == 0)
                    dp[i][j] = matrix[i][j] - '0';
                // 状态转移
                else {
                    if (matrix[i][j] == '0')
                        dp[i][j] = 0;
                    else
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                // 存储最大值
                if (dp[i][j] > max)
                    max = dp[i][j];
            }
        return max * max;
    }
}